/**
 * 
 */
package logic.algorithm;

import java.util.LinkedList;
import java.util.List;

import datamodel.Grid;
import datamodel.GridElement;
import datamodel.GridElementAlgoState;
import datamodel.Grid.Neighbors;
import datamodel.GridElementState;

/**
 * @author Marc, Kevin Munk
 * @version 0.1
 *
 */
public class DijkstraAlgorithm implements Algorithm {
	
	List<GridElement> queue;
	Grid grid;
	GridElement startGrid;
	GridElement endGrid;

	@Override
	public void init(Grid grid) {
		
		// Initialisierung der Warteschlange ...
		this.grid = grid;
		queue = new LinkedList<GridElement>();
		startGrid = grid.getStartElement();
		endGrid = grid.getEndElement();
		
		// Alle Knoten setzen
		for(int row = 0; row < grid.getRows(); row++) {
			for(int column = 0; column < grid.getColumns(); column++) {
				GridElement node = grid.getElementAt(row, column);
				
				node.setDistance(Integer.MAX_VALUE);
				node.setPrevious(null);
				node.setAlgoState(GridElementAlgoState.NONE);
			}
		}
		
		startGrid.setDistance(0);
		startGrid.setAlgoState(GridElementAlgoState.LOOKED_AT);
		
		// Entfernung zu den Nachbarknoten setzen
		Neighbors neighbors = grid.getNeighborsFrom(startGrid, true);
		for(int n = 0; n < neighbors.getNeighbors().size(); n++) {
			GridElement neighborNode = neighbors.getNeighbors().get(n);
			
			if(!neighborNode.getState().equals(GridElementState.BLOCKED)) {
				queue.add(neighborNode);
				neighborNode.setDistance(neighbors.getWayCosts().get(n));
				neighborNode.setPrevious(startGrid);
			}
		}
	}
	
	@Override
	public boolean doNextStep() {
		while(!queue.isEmpty() && !endGrid.getAlgoState().equals(GridElementAlgoState.LOOKED_AT)) {
			
			// Knoten mit minimalen Wegkosten finden, aber warum mit <= statt einfach nur <???
			GridElement minNode = queue.get(0);
			for(GridElement node: queue) {
				if(node.getDistance() <= minNode.getDistance()) {
					minNode = node;
				}
			}
			
			queue.remove(minNode);
			minNode.setAlgoState(GridElementAlgoState.LOOKED_AT);
			
			// Nachbarknoten von minNode
			Neighbors neighbors = grid.getNeighborsFrom(minNode, true);
			for(int n = 0; n < neighbors.getNeighbors().size(); n++) {
				GridElement neighborNode = neighbors.getNeighbors().get(n);
				int edge = minNode.getDistance() + neighbors.getWayCosts().get(n);
				
				if(!neighborNode.getState().equals(GridElementState.BLOCKED)) {
					
					if(neighborNode.getDistance() == Integer.MAX_VALUE) {
						queue.add(neighborNode);
					} 
					if(edge < neighborNode.getDistance()) {
						neighborNode.setDistance(edge);
						neighborNode.setPrevious(minNode);
					}
				}
			}
		}
		if(queue.isEmpty())
			return false;
		else return !isSolved(); 
	}

	@Override
	public boolean isSolved() {
		return endGrid.getAlgoState().equals(GridElementAlgoState.LOOKED_AT);
	}

}
